class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if len(p) == 0:
            return len(s) == 0
        s_len = len(s)
        p_len = len(p)

        dp = [[False for _ in range(p_len+1)] for _ in range(s_len+1)]
        dp[0][0] = True

        for i in range(2, p_len+1, 2):
            dp[0][i] = (dp[0][i-2] and p[i-1] == "*")

        for i in range(1, s_len+1):
            for j in range(1, p_len+1):
                if p[j-1] == "*":
                    # 匹配0次
                    if j>=2:
                        dp[i][j] = dp[i][j-2]

                    if i>=1 and j>=2 and (s[i-1]==p[j-2] or p[j-2]=="."):
                        dp[i][j] |=  dp[i-1][j]
                elif s[i-1] == p[j-1] or p[j-1] == ".":
                    dp[i][j] = dp[i-1][j-1]
        return dp[s_len][p_len]

if __name__ == '__main__':
    Solution().isMatch("aab", "c*a*b")
